<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    var findDuplicate = function (nums) {
      const n = nums.length;
      let l = 1,
        r = n - 1,
        ans = -1;
      while (l <= r) {
        let mid = (l + r) >> 1;
        let cnt = 0;
        for (let i = 0; i < n; ++i) {
          cnt += nums[i] <= mid;
        }
        if (cnt <= mid) {
          l = mid + 1;
        } else {
          r = mid - 1;
          ans = mid;
        }
      }
      return ans;
    };


    // function leftBinSearch (num, target) {
    //   let low = 0, high = num.length 

    //   while(low < high) {
    //     let mid = (low + high) >> 1

    //     if(num[mid] < target) {
    //       low = mid + 1
    //     }else if(num[mid] > target) {
    //       high = mid
    //     }else if(num[mid] == target) {
    //       high = mid
    //     }
    //   }

    //   if(low >= num.length || num[low] !== target) return -1;

    //   return low;

    // }

    var rightBinSearch = function (num, target) {
      let low = 0,
        high = num.length

      while (low < high) {
        let mid = (low + high) >> 1;
        if (num[mid] > target) {
          high = mid
        } else if (target > num[mid]) {
          low = mid + 1
        } else if (target == num[mid]) {
          low = mid + 1
        }
      }
      if (high - 1 >= num.length || num[high - 1] !== target) return -1;

      return high - 1
    }


    var leftRight = function (num, target) {
      let left = leftBinSearch(num, target)
      let right = rightBinSearch(num, target)

      console.log([left, right]);
    }
    /**
     * @param {number[]} nums
     * @return {number}
     */
    var singleNonDuplicate = function (nums) {
      let low = 0,
        high = nums.length;
      while (low < high) {
        let cnt = 0
        let mid = (low + high) >> 1;

        for (let i = 0; i < nums.length; i++) {
          cnt += nums[i] <= nums[mid]
        }

        if (cnt % 2 > 0) {
          high = mid
        } else {
          low = mid + 1
        }
      }

      return nums[low]
    };


    let num = [1, 2, 2, 2, 3, 4]

    leftBinSearch(num, 2)

    let res = findDuplicate([2, 4, 5, 8, 3, 1, 2, 7])


    var binSearch = function (num, target) {

      let low = 0,
        high = num.length - 1

      while (low < high) {
        let mid = (low + high) >> 1

        if (num[mid] == target) {
          return mid
        } else if (num[mid] < target) {
          low = mid + 1
        } else {
          high = mid - 1
        }
      }

      return -1
    }

    function leftBinSearch(nums, target) {
      let low = 0,
        high = nums.length;

      while (low < high) {
        let mid = low + ((high - low) >> 1)

        if (nums[mid] == target) {
          high = mid
        } else if (nums[mid] < target) {
          high = mid
        } else {
          low = mid + 1
        }
      }

      if (nums[low] != target || low >= num.length) return -1

      return low
    }

    var searchLeft = function (nums, target) {
      let low = 0,
        high = nums.length - 1

      while (low < high) {
        let mid = (low + high) >> 1;

        if (target > nums[mid]) {
          low = mid + 1
        } else if (target < nums[mid]) {
          high = mid
        } else {
          high = mid
        }
      }

      if (low >= nums.length || nums[low] !== target) return -1;

      return low
    }


    var findClosestElements = function (arr, k, x) {
      let low = 0,
        high = arr.length - k;

      while (low < high) {
        let mid = low + ((high - low) >> 1)

        let res = Math.abs(arr[mid] - x) < Math.abs(arr[mid + k] - x)
        if (res) {
          low = mid + 1
        } else {
          high = mid

        }
      }


      return arr.splice(low, k)
      // return [low]
    };


    // 排序算法

    // 冒泡 算法



    function randomArr(num) {
      let arr = []
      for (let i = 0; i < num; i++) {
        arr[i] = Math.floor(Math.random() * (num + 1))
      }
      return arr
    }

    let newArr = randomArr(10000)


    function swap(arr, a, b) {
      let tmp = arr[a];
      arr[a] = arr[b];
      arr[b] = tmp;
    }

    function bubbleSort(arr) {
      let start = +new Date()
      console.time('bubble start')
      let allNum = 0;
      let swapNum = 0
      for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1; j++) {
          if (arr[j] > arr[j + 1]) {
            swap(arr, j, j + 1)
          }
        }
      }
      console.timeEnd('bubble start')

      console.log(+new Date() - start, 'bubble time');
    }


    function selectSort(arr) {
      let start = +new Date()
      console.time('select start')
      let min
      for (let i = 0; i < arr.length - 1; i++) {
        min = i;
        for (let j = i + 1; j < arr.length; j++) {
          if (arr[min] > arr[j]) {
            min = j
          }
        }
        swap(arr, i, min)
      }
      console.timeEnd('select start')

      console.log(+new Date() - start, 'select time');
    }


    function insertSort(arr) {
      let start = +new Date()
      console.time('insert start')
      let tmp, inner;

      for (let outer = 1; outer < arr.length; outer++) {
        const tmp = arr[outer];
        let inner = outer

        while (inner > 0 && arr[inner - 1] > tmp) {
          arr[inner] = arr[inner - 1]
          inner--
        }
        arr[inner] = tmp
      }

      console.timeEnd('insert start')

      console.log(+new Date() - start, 'insert time');
    }

    // insertSort(arr)



    // var isAnagram = function(s, t) {
    //   if(!s || !t) return false;
    //   const ns = insertSorts(s.split(''))
    //   const nt = insertSorts(t.split(''))
    //   return ns.join() === nt.join()
    // };

    var isAnagram = function (s, t) {
      if (!s && !t) return true;
      if (!s || !t) return false;

      const ns = s.split('')
      const nt = t.split('')

      ns.sort((a, b) => a - b)
      nt.sort((a, b) => a - b)
      return ns.join() === nt.join()
    };


    var insertSorts = function (str) {
      let inner, tmp

      for (let outer = 1; outer < str.length; outer++) {
        tmp = str[outer]
        inner = outer

        while (inner > 0 && str[inner - 1] > tmp) {
          str[inner] = str[inner - 1];
          inner--;
        }
        str[inner] = tmp
      }
      return str
    }


    var sortArrayByParityII = function (A) {
      let arr = Array(A.length)

      let index = 0
      for (let i = 0; i < A.length; i++) {
        if (A[i] % 2 == 0) {
          arr[index] = A[i]
          index += 2
        }
      }

      index = 1
      for (let i = 0; i < A.length; i++) {
        if (A[i] % 2 == 1) {
          arr[index] = A[i]
          index += 2
        }
      }
      return arr
    };



    var bubbleSort1 = (arr) => {

      for (let outer = 0; outer < arr.length; outer++) {
        const element = arr[outer];
        
        for (let inner = 0; inner < arr.length - 1 - outer; inner++) {
          if(arr[inner] > arr[inner + 1]) {
            swap(arr, inner, inner+1)
          }
          
        }
      }
    }


    var selectSort1 = (arr) => {
      let min;

      for (let outer = 0; outer < arr.length; outer++) {
        min = outer
        for (let inner = outer + 1; inner < arr.length; inner++) {
          if(arr[inner] < arr[min]) {
            min = inner
          }
        }
        swap(arr, outer, min)
      }
    }


    var insertSort1 = (arr) => {
      let tmp, inner;

      for (let outer = 1; outer < arr.length; outer++) {
        inner = outer
        tmp = arr[outer]
        while(inner > 0 && arr[inner - 1] > tmp) {
          arr[inner] = arr[inner - 1]
          inner--
        }
        arr[inner] = tmp
      }
    }



  </script>
</body>

</html>